import numpy as np
vecteur = np.array([1,2,3,4])
print(type(vecteur))<class 'numpy.ndarray'>
Pour ce TP noté, vous devrez charger votre fichier sur Moodle, avant 22h, jeudi 09/03/2023.
Pour ce travail vous devez déposer un unique fichier au format .py, structuré avec des cellules, dont le nom est tp_note_HAX606X_Prenom_Nom.py. Vous remplirez votre nom, prénom de manière adéquate. Si le nom de fichier ne suit pas cette forme, vous perdez 1 pt.
De plus, les personnes qui n’auront pas soumis leur devoir sur Moodle avant la limite obtiendront comme note zéro. Ainsi, pensez à soumettre une version provisoire par sécurité…
La note totale est sur 20 points répartis comme suit :
$$
Pour un vecteur x\in\mathbb{R}^d, on rappelle que la norme euclidienne est \left \lVert x \right \rVert_2=\sqrt{\sum_{i=1}^d x_i^2} et la norme infinie est donnée par \left \lVert x \right \rVert_\infty = \max(\left \vert x_i \right \vert, i=1,\dots,d).
On donne ici l’algorithme de descente de gradient pour une fonction différentiable f:\mathbb{R}^d \to \mathbb{R},
\begin{algorithm}
\caption{Descente de gradient}
\begin{algorithmic}
\INPUT $\nabla f~(\texttt{function}), x_{\rm init}~(\texttt{numpy.ndarray}), \gamma~(\texttt{float}), \epsilon~(\texttt{float}), n_{\rm iter}~(\texttt{int})$
\STATE $x \gets x_{\rm init}$
\COMMENT{Initialization}
\FOR{$i=1,\dots,n_{\rm iter}$}
\STATE $g \gets \displaystyle \nabla f (x)$
\IF{$\|g\|_{\infty} \leq \epsilon$}
\STATE Break
\ENDIF
\STATE $x \gets x - \gamma g$
\ENDFOR
\OUTPUT $x$
\end{algorithmic}
\end{algorithm}
Adapter et coder en Python l’Algorithme ci-dessus pour avoir en sortie la liste de tous les itérés de la descente de gradient. Pour ce faire, on veillera à ce que le code puisse traiter le cas d’un vecteur x\in\mathbb{R}^d avec d quelconque, et pas uniquement le cas bi-dimensionnel (cf. question suivante). Pour vous aider, les éléments entre parenthèses indiquent le type des entrées/sorties, type que l’on obtient par exemple avec la commande type:
import numpy as np
vecteur = np.array([1,2,3,4])
print(type(vecteur))<class 'numpy.ndarray'>
Proposez un test de l’algorithme sur une fonction simple (par exemple quadratique) avec un espace de départ de dimension d=23.
Prenons f:x\mapsto (x-1)^2. Utiliser la fonction subplots de matplotlib pour créer deux graphiques l’un au dessus de l’autre, en affichant les 15 premiers itérés avec un pas de 0.1 et une tolérance de 10^{-15}, et une initialisation x_{\rm init} = x_0= -1/2:
L’axe des abscisses sera partagé entre les deux figures en utilisant l’argument sharex de la fonction subplots. Le résultat attendu pourra s’inspirer de la Figure 1 ci-dessous.
Afficher sur un même graphique les lignes de niveaux de la fonction de Rosenbrock f_{\mathit{ros}} en dimension d=2:
\begin{align*}
f_{\mathit{ros}}:
\begin{pmatrix}
x_1 \\
x_2
\end{pmatrix}
\mapsto
(x_1 - 1) ^ 2 + 100 \cdot (x_2-x_1^2) ^ 2 \enspace,
\end{align*}
ainsi que tous les itérés de l’algorithme de descente de gradient pour n_{\rm iter}=30, \epsilon=10^{-10} en partant du point x_{\rm init}=(-1, -0.5) et pour deux choix de pas \gamma=10^{-5} ou \gamma=10^{-3}. On pourra par exemple utiliser scipy.optimize.rosen_der pour cela. Pour l’affichage graphique, on pourra s’inspirer de l’exemple donné ci-dessous:
La méthode de recherche linéaire (🇬🇧: line search) permet de multiplier ou de diviser \gamma_k, la taille du pas courant à l’itération k, d’un facteur \tau, si la fonction n’a pas assez décru (ce qui est quantifié par un nouveau paramètre \alpha).
\begin{algorithm}
\caption{Descente de gradient avec recherche linéaire }
\begin{algorithmic}
\INPUT $f~(\texttt{function})$,$\nabla f~(\texttt{function})$,$ x_{\rm init}~(\texttt{numpy.ndarray})$,$ \gamma~(\texttt{float})$,$ \epsilon~(\texttt{float})$,$ n_{\rm iter}~(\texttt{int})$,$ \alpha~(\texttt{float})$,$ \tau~(\texttt{float})$ \\
\STATE $x \gets x_{\rm init}$
\COMMENT{Initialization}
\FOR{$i=1,\dots,n_{\rm iter}$}
\STATE $g \gets \displaystyle \nabla f (x)$
\IF{$\|g\|_{\infty} \leq \epsilon$}
\STATE Break
\ENDIF
\STATE $z \gets x - \gamma g$
\IF{$f(z) \leq f(x) - \alpha \gamma \|g\|_2^2$}
\STATE $x \gets z $
\STATE $\gamma \gets \gamma /\tau $
\ELSE
\STATE $\gamma \gets \tau \gamma $
\ENDIF
\ENDFOR
\OUTPUT $x~(\texttt{numpy.ndarray})$
\end{algorithmic}
\end{algorithm}
Adapter et coder en Python l’algorithme ci-dessus pour avoir en sortie la liste de tous les itérés obtenus par la descente de gradient avec recherche linéaire, mais aussi la liste de tous les pas \gamma_k utilisés. Dans la suite on utilisera \alpha =0.5, \tau=0.5.
La méthode du pas adaptatif permet d’adapter la taille du pas courant \gamma_k de manière plus souple que la méthode précédente. Représenter sur un même graphique l’évolution de la taille des pas au cours des itérations pour les trois algorithmes introduits.
\begin{algorithm}
\caption{Descente de gradient avec recherche linéaire }
\begin{algorithmic}
\INPUT $\nabla f~(\texttt{function})$,$ x_{\rm init}~(\texttt{numpy.ndarray})$,$ \gamma~(\texttt{float})$,$ \epsilon~(\texttt{float})$,$ n_{\rm iter}~(\texttt{int})$ \\
\COMMENT{Initialization}
\STATE $\gamma_0 \gets \gamma$
\STATE $x_0 \gets x_{\rm init}$
\STATE $x_1 \gets x_{0} - \gamma_0 \nabla f(x_0)$
\STATE $\theta_0 \gets +\infty$
\FOR{$i=1,\dots,n_{\rm iter}$}
\STATE $\gamma_k \gets \min \left(\sqrt{1+\theta_{k-1}} \gamma_{k-1},\frac{1}{2} \frac{\|x_k - x_{k-1}\|}{\|
\nabla f (x_k) - \nabla f (x_{k-1})\|} \right)$
\STATE $g \gets \displaystyle \nabla f (x_k)$
\IF{$\|g\|_{\infty} \leq \epsilon$}
\STATE Break
\ENDIF
\STATE $x_{k+1} \gets x_k - \gamma_k g$
\STATE $\theta_k \gets \frac{\gamma_k}{\gamma_{k-1}} $
\ENDFOR
\OUTPUT $x_k ~(\texttt{numpy.ndarray})$
\end{algorithmic}
\end{algorithm}
La méthode du pas adaptatif permet d’adapter la taille du pas courant \gamma_k de manière plus souple. Représenter sur un même graphique l’évolution de la taille des pas au cours des itérations, et ce pour les trois algorithmes introduits.
Le minimum global de la fonction de Rosenbrock f_{ros} est atteint en x^\star = (1,1), c’est-à-dire:
x^\star \in \displaystyle\operatorname*{argmin}_{x\in\mathbb{R}^2}f_{ros}(x) \enspace.
Pour une fonction g, la notation x^* \in \displaystyle\operatorname*{argmin}_{x}g(x) signifie que x^* est un point qui atteint la valeur \displaystyle\min_{x}g(x), ainsi: g(x^*)=\displaystyle\min_{x}g(x).
Comparer la convergence de ces trois méthodes de la manière suivante :
py.Pour améliorer la lisibilité du graphique, nous rappelons que l’usage d’une échelle logarithmique sur la mesure observée peut être utile.